/*
 * @lc app=leetcode.cn id=39 lang=golang
 *
 * [39] 组合总和
 */

// @lc code=start
func combinationSum(candidates []int, target int) [][]int {
	ans := [][]int{}
	n := len(candidates)

	var dfs func(index, sum int)
	cur := []int{}
	dfs = func(index, sum int) {

		if sum == 0 {
			ans = append(ans, append([]int{}, cur...))
			return
		}
		for i := index; i < n; i++ {
			if sum < candidates[i] {
				continue
			}
			cur = append(cur, candidates[i])
			dfs(i, sum-candidates[i])
			cur = cur[:len(cur)-1]
		}
	}
	dfs(0, target)
	return ans
}

// @lc code=end

